package tp78.graph.lastVersion;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import org.omg.PortableInterceptor.CurrentOperations;

public class Graph<V, E extends ArcGraph> extends GraphAdjList<V, E> {

	@Override
	public void addArc(V v, V w, E e) {
		super.addArc(v, w, e);
		super.addArc(w, v, e);
	}
	
	@Override
	public void removeArc(V v, V w) {
		super.removeArc(v, w);
		super.removeArc(w, v);
	}
	
	public int degree(V v) {
		Node node = nodes.get(v);
		if (node != null) {
			return node.adj.size();
		}
		return 0;
	}

	public boolean isConnected() {
		if (isEmpty()) {
			return true;
		}
		clearMarks();
		List<Node> l = getNodes();
		List<V> laux = new ArrayList<V>();
		DFS(l.get(0), laux);
		for (Node node : l) {
			if (!node.visited) {
				return false;
			}
		}
		return true;
	}
	
	public int connectedComponents() {
		clearMarks();
		return pathCount();
	}
	
	private int pathCount() {
		int count = 0;
		Node node;
		while ((node = unvisited()) != null) {
			count++;
			DFS(node, new ArrayList<V>());
		}
		return count;
	}

	private Node unvisited() {
		for(Node node : getNodes()) {
			if (! node.visited )
				return node;
		}
		return null;
	}
	
	public boolean cutVertex(V vertex) {
		Node node = nodes.get(vertex);
		if (node == null || node.adj.size() == 0)
			return false;
		clearMarks();
		int components = pathCount();
		clearMarks();
		node.visited = true;
		return components != pathCount();
	}
	
	public boolean isBridge(V v, V w) {
		E e = isArc(v,w);
		if ( e == null)
			return false;
		int components = connectedComponents();
		removeArc(v, w);
		int newComponents = connectedComponents();
		addArc(v, w, e);
		return components != newComponents;
		
	}
	
	/**
	 * Practica
	 * 
	 */
	public void DFS(V start,Function<V> f){
		Node s=nodes.get(start);
		if(s==null){
			return;
		}
		DFS(s,f);
		clearMarks();
	}
	
	private void DFS(Node current,Function<V> f){
		if(current.visited){
			return;
		}
		current.info=f.evaluate(current.info);
		current.visited=true;
		
		for(Arc e : current.adj){
			if(!e.neighbor.visited){
				DFS(e.neighbor,f);
			}
		}
	}
	
	public void BFS(V start,Function<V> f){
		Node s=nodes.get(start);
		if(s==null){
			return;
		}
		
		BFS(s,f);
		clearMarks();
	}
	
	private void BFS(Node current,Function<V> f){
		if(current.visited){
			return;
		}
		current.visited=true;
		
		for(Arc e:current.adj){
			if(!e.neighbor.visited){
				e.neighbor.info=f.evaluate(e.neighbor.info);
			}
		}
		
		for(Arc e:current.adj){
			BFS(e.neighbor,f);
		}
	}
	
	public List<V> IterativeDFS(V start){
		Node current=nodes.get(start);
		if(current==null){
			return null;
		}
		List<V> list=new LinkedList<V>();
		Deque<Node> stack=new LinkedList<Node>();
		stack.push(current);
		clearMarks();
		
		while(!stack.isEmpty()){
			current=stack.pop();
			if(!current.visited){
				list.add(current.info);
				current.visited=true;
			}
			
			for(Arc e:current.adj){
				if(!e.neighbor.visited){
					stack.push(current);
				}
			}
		}
		return list;
	}
	
	public Graph<V,E> spanningTree(V start){
		Node current=nodes.get(start);
		if(current==null){
			return null;
		}
		
		Deque<Node> q=new LinkedList<Node>();
		Graph<V,E> aux=new Graph<V,E>();
		clearMarks();
		
		q.offer(current);
		while(!q.isEmpty()){
			current=q.poll();
			
			if(!current.visited){
				aux.AddVertex(current.info);
				current.visited=true;
			}
			
			for(Arc e:current.adj){
				q.offer(e.neighbor);
				aux.addArc(current.info,e.neighbor.info,e.info);
			}
		}
		return aux;
	}
	
	public boolean sixDegreesOfSeparation(){
		for(Node n:nodeList){
			clearMarks();
			if(BFS_count(n,6) != nodes.size()){
				return false;
			}
		}
		return true; 
	}
	
	private int BFS_count(Node start,int maxHeight){
		Deque<Node> q=new LinkedList<Node>();
		int count=0;
		
		start.tag=0;
		q.offer(start);
		Node current;
		
		while(!q.isEmpty()){
			current=q.poll();
			if(!current.visited){
				current.visited=true;
				count++;
			}
			if(current.tag>maxHeight){
				return count;
			}
			for(Arc e:current.adj){
				if(!e.neighbor.visited){
					q.offer(e.neighbor);
					e.neighbor.tag=current.tag+1;
				}
			}
		}
		return count;		
	}
	
	public List<V> possibleFriends(V start,int limit){
		Node current=nodes.get(start);
		if(current==null){
			return null;
		}
		clearMarks();
		List<V> list=new LinkedList<V>();
		Deque<Node> q=new LinkedList<Node>();
		current.tag=0;
		q.offer(current);
		
		while(!q.isEmpty()){
			current=q.poll();
			
			if(!current.visited){
				current.visited=true;
				list.add(current.info);
			}else if(current.tag>limit){
				return list;
			}
			
			for(Arc e:current.adj){
				if(!e.neighbor.visited){
					q.offer(e.neighbor);
					e.neighbor.tag=current.tag+1;
				}
			}	
		}
		return list;
	}

	

}

